/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-21
 * Time: 21:29
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ClosestPointsDivideConquer {
    static class Point {
        double x, y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    // 计算两点距离（为避免开方耗时，可先比较平方距离）
    private static double distance(Point p1, Point p2) {
        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        return dx * dx + dy * dy; // 先返回平方距离，最后再开方
    }

    // 暴力求解小规模点集的最近距离（分治的 base case）
    private static double bruteForce(List<Point> points, int left, int right) {
        double minDist = Double.POSITIVE_INFINITY;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                double dist = distance(points.get(i), points.get(j));
                if (dist < minDist) {
                    minDist = dist;
                }
            }
        }
        return minDist;
    }

    // 分治算法核心
    private static double closest(List<Point> points, int left, int right) {
        // 若点数量小于等于3，直接暴力求解
        if (right - left + 1 <= 3) {
            return bruteForce(points, left, right);
        }

        // 找中点，划分左右两部分
        int mid = (left + right) / 2;
        Point midPoint = points.get(mid);

        // 递归求解左右两部分的最近距离
        double leftMin = closest(points, left, mid);
        double rightMin = closest(points, mid + 1, right);

        // 取左右两部分的最小值
        double minDist = Math.min(leftMin, rightMin);

        // 收集距离中线x坐标小于minDist的点（可能存在跨区域的更近点对）
        List<Point> strip = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            double dx = points.get(i).x - midPoint.x;
            if (dx * dx < minDist) { // 平方距离小于当前最小值
                strip.add(points.get(i));
            }
        }

        // 检查strip中是否存在更近的点对（最多比较6个点，证明略）
        double stripMin = checkStrip(strip, minDist);
        return Math.min(minDist, stripMin);
    }

    // 检查strip中的点对，更新最小距离
    private static double checkStrip(List<Point> strip, double minDist) {
        int n = strip.size();
        double min = minDist;

        // 按y坐标排序（优化比较效率）
        Collections.sort(strip, Comparator.comparingDouble(p -> p.y));

        // 每个点最多与后面6个点比较（几何性质保证）
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && (strip.get(j).y - strip.get(i).y) * (strip.get(j).y - strip.get(i).y) < min; j++) {
                double dist = distance(strip.get(i), strip.get(j));
                if (dist < min) {
                    min = dist;
                }
            }
        }
        return min;
    }

    // 对外接口：先按x坐标排序，再调用分治函数
    public static double findClosest(List<Point> points) {
        if (points.size() < 2) return Double.POSITIVE_INFINITY;
        // 按x坐标排序（分治的前提）
        Collections.sort(points, Comparator.comparingDouble(p -> p.x));
        return Math.sqrt(closest(points, 0, points.size() - 1)); // 最后开方得到实际距离
    }

    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        points.add(new Point(1, 2));
        points.add(new Point(3, 4));
        points.add(new Point(5, 1));
        points.add(new Point(7, 3));
        points.add(new Point(2, 5));

        System.out.println("最近点对距离（分治算法）：" + findClosest(points)); // 输出约2.236
    }
}